package com.github.yangyishe.p400;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 373. 查找和最小的 K 对数字
 * https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
 *
 * 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
 *
 * 请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
 * 输出: [1,2],[1,4],[1,6]
 * 解释: 返回序列中的前 3 对数：
 *      [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
 * 示例 2:
 *
 * 输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
 * 输出: [1,1],[1,1]
 * 解释: 返回序列中的前 2 对数：
 *      [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
 * 示例 3:
 *
 * 输入: nums1 = [1,2], nums2 = [3], k = 3
 * 输出: [1,3],[2,3]
 * 解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
 *
 *
 * 提示:
 *
 * 1 <= nums1.length, nums2.length <= 105
 * -109 <= nums1[i], nums2[i] <= 109
 * nums1 和 nums2 均为 升序排列
 * 1 <= k <= 104
 * k <= nums1.length * nums2.length
 */
public class Problem373 {
    public static void main(String[] args) {
        int[] nums1=new int[]{1,2};
        int[] nums2=new int[]{3};
        int k=2;

        Problem373 problem373 = new Problem373();
        List<List<Integer>> pairs = problem373.kSmallestPairs(nums1, nums2, k);
        System.out.println("pairs = " + pairs);

    }

    /**
     * 思路:
     * 分别对nums1和nums2进行top-k堆化
     * 分别对两个堆进行从小到大排序
     * 分离双指针分别取两个堆的左侧, 之后遍历获取最小值
     *
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //1. 分别创建堆
        int[] heap1 = createBigHeap(nums1, Math.min(nums1.length,k));
        int[] heap2 = createBigHeap(nums2, Math.min(nums2.length,k));

        //2. 堆排序
        Arrays.sort(heap1);
        Arrays.sort(heap2);

        //3. 双指针遍历

        return createMinSumList(heap1,heap2,k);
    }

    /**
     * heap1和heap2可以构建成一个事实上的二维数组.
     * 每次需要比较是否为最小的, 即边界值.
     * 如第一次比较0-0,第二次比较0-1,1-0
     * 第2次:如果0-1更大, 第三次比较0-2,1-0
     * 第2次:如果1-0更大, 第三次比较0-1,1-1,2-0
     * 以此类推
     * @param heap1
     * @param heap2
     * @param k
     * @return
     */
    private List<List<Integer>> createMinSumList(int[] heap1, int[] heap2, int k) {
        // 访问记录.索引表示heap2的索引;值表示heap1的索引;
        int[] visits=new int[heap2.length];
        List<List<Integer>> resultListList=new ArrayList<>();
        while(k-->0){
            int min=Integer.MAX_VALUE;
            boolean visitZero=false;
            int minRow=0;
            int row=0;
            while(!visitZero){
                if(row>=heap2.length){
                    break;
                }
                if(visits[row]>=heap1.length){
                    row++;
                    continue;
                }
                if(visits[row]==0){
                    visitZero=true;
                }
                int eachMin = heap1[visits[row]] + heap2[row];
                if(eachMin <min){
                    min=eachMin;
                    minRow=row;
                }
                row++;
            }
            if(visits[minRow]>=heap1.length){
                break;
            }
            resultListList.add(Arrays.asList(heap1[visits[minRow]],heap2[minRow]));
            visits[minRow]++;

        }

        return resultListList;
    }

    /**
     * 创建大顶堆
     * @param nums
     * @param k
     * @return
     */
    private int[] createBigHeap(int[] nums,int k){
        // 创建堆原型
        int[] heap=new int[k];

        // 填充k个数并堆化
        for(int i=0;i<k;i++){
            heap[i]=nums[i];
        }
        for(int i=heap.length-1;i>=0;i--){
            siftDown(heap,i);
        }

        // 遍历其后的元素
        for(int i=k+1;i<nums.length;i++){
            if(nums[i]<heap[0]){
                heap[0]=nums[i];
                siftDown(heap,0);
            }
        }

        return heap;
    }

    private void siftDown(int[] heap, int i) {
        while(true){
            int left=i*2+1;
            int right=i*2+2;
            if(left>=heap.length){
                return;
            }
            // 获得较大的分支(因为要构建大顶堆,需要保证父节点大于子节点)
            int maxBot;
            if(right>=heap.length){
                maxBot=left;
            }else{
                maxBot=heap[left]>heap[right]?left:right;
            }
            if(heap[i]>=heap[maxBot]){
                return;
            }
            swap(heap,i,maxBot);
            i=maxBot;
        }
    }

    private void swap(int[] heap, int i, int maxBot) {
        int temp=heap[i];
        heap[i]=heap[maxBot];
        heap[maxBot]=temp;
    }
}
